6.6 KB · ⇊ 5 parts · ⤓ Micron 6.6 KB · ⤓ HTML 40.1 KB

top

Generalized balanced ternary is a generalization of the balanced ternary numeral system to represent points in a higher-dimensional space. It was first described in 1982 by Laurie Gibson and Dean Lucas.cite-ref-1[1] It has since been used for various applications, including geospatialcite-ref-2[2] and high-performance scientificcite-ref-3[3] computing.

• General form

• One dimension

• Addition table

• Two dimensions

• Addition table

• See also

• References

• External links

Like standard positional numeral systems, generalized balanced ternary represents a point p {\displaystyle p} as powers of a base B {\displaystyle B} multiplied by digits d i {\displaystyle d_{i}} .

p = d 0 + B d 1 + B 2 d 2 + … … {\displaystyle p=d_{0}+Bd_{1}+B^{2}d_{2}+\ldots }

Generalized balanced ternary uses a transformation matrix as its base B {\displaystyle B} . Digits are vectors chosen from a finite subset { D 0 = 0 , D 1 , … … , D n } {\displaystyle \{D_{0}=0,D_{1},\ldots ,D_{n}\}} of the underlying space.

In one dimension, generalized balanced ternary is equivalent to standard balanced ternary, with three digits (0, 1, and −1). B {\displaystyle B} is a 1 × × 1 {\displaystyle 1\times 1} matrix, and the digits D i {\displaystyle D_{i}} are length-1 vectors, so they appear here without the extra brackets.

B = 3 D 0 = 0 D 1 = 1 D 2 = − − 1 {\displaystyle {\begin{aligned}B&=3\\D_{0}&=0\\D_{1}&=1\\D_{2}&=-1\end{aligned}}}

This is the same addition table as standard balanced ternary, but with D 2 {\displaystyle D_{2}} replacing T. To make the table easier to read, the numeral i {\displaystyle i} is written instead of D i {\displaystyle D_{i}} .

Addition + 0 1 2 0 0 1 2 1 1 12 0 2 2 0 21

In two dimensions, there are seven digits. The digits D 1 , … … , D 6 {\displaystyle D_{1},\ldots ,D_{6}} are six points arranged in a regular hexagon centered at D 0 = 0 {\displaystyle D_{0}=0} .cite-ref-van-roessel-4-0[4]

B = 1 2 [ 5 3 − − 3 5 ] D 0 = 0 D 1 = ( 0 , 3 ) D 2 = ( 3 2 , − − 3 2 ) D 3 = ( 3 2 , 3 2 ) D 4 = ( − − 3 2 , − − 3 2 ) D 5 = ( − − 3 2 , 3 2 ) D 6 = ( 0 , − − 3 ) {\displaystyle {\begin{aligned}B&={\frac {1}{2}}{\begin{bmatrix}5&{\sqrt {3}}\\-{\sqrt {3}}&5\end{bmatrix}}\\D_{0}&=0\\D_{1}&=\left(0,{\sqrt {3}}\right)\\D_{2}&=\left({\frac {3}{2}},-{\frac {\sqrt {3}}{2}}\right)\\D_{3}&=\left({\frac {3}{2}},{\frac {\sqrt {3}}{2}}\right)\\D_{4}&=\left(-{\frac {3}{2}},-{\frac {\sqrt {3}}{2}}\right)\\D_{5}&=\left(-{\frac {3}{2}},{\frac {\sqrt {3}}{2}}\right)\\D_{6}&=\left(0,-{\sqrt {3}}\right)\\\end{aligned}}}

As in the one-dimensional addition table, the numeral i {\displaystyle i} is written instead of D i {\displaystyle D_{i}} (despite e.g. D 2 {\displaystyle D_{2}} having no particular relationship to the number 2).

Additioncite-ref-van-roessel-4-1[4] + 0 1 2 3 4 5 6 0 0 1 2 3 4 5 6 1 1 12 3 34 5 16 0 2 2 3 24 25 6 0 61 3 3 34 25 36 0 1 2 4 4 5 6 0 41 52 43 5 5 16 0 1 52 53 4 6 6 0 61 2 43 4 65

If there are two numerals in a cell, the left one is carried over to the next digit. Unlike standard addition, addition of two-dimensional generalized balanced ternary numbers may require multiple carries to be performed while computing a single digit.cite-ref-van-roessel-4-2[4]

• Gosper curve

cite-note-11. ↑ citerefgibsonlucas1982Gibson, Laurie; Lucas, Dean (1982). "Spatial Data Processing Using Generalized Balanced Ternary". Proceedings of the IEEE Computer Society Conference on Pattern Recognition and Image Processing: 566–571.

cite-note-22. ↑ citerefsahr2011Sahr, Kevin (2011-01-01). "Hexagonal Discrete Global Grid Systems for Geospatial Computing" (PDF). Archives of Photogrammetry, Cartography and Remote Sensing. 22: 363. Bibcode:2011ArFKT..22..363S.

cite-note-33. ↑ citerefde-kinderbarnes1997de Kinder, R. E. Jr.; Barnes, J. R. (August 1997). "The Generalized Balanced Ternary (GBT) Applied to High-Performance Computational Algorithms". APS Meeting Abstracts. Bibcode:1997APS..CPC..C409D.

cite-note-van-roessel-44. ↑ citerefvan-roessel1988van Roessel, Jan W. (1988). "Conversion of Cartesian coordinates from and to Generalized Balanced Ternary addresses" (PDF). Photogrammetric Engineering and Remote Sensing. 54: 1565–1570.

• Spiral Honeycomb Mosaic, another name for the two-dimensional form of this numbering system

• "Clever Hex Grid Method" discussion on rec.games.roguelike.development